package com.syedu.day05.homework;

/**
 * description：汉诺塔问题
 *
 * 一共三根柱子A,B,C
 * 一个盘子     1A->C
 * 两个盘子     1A->B    2A->C    1B->C
 * 三个盘子     1A->C    2A->B    1C->B     3A-C    1B->A   2B->C   1A->C
 * ...
 * n个盘子
 * 1~n-1的盘子看做是一个整体,然后每次递归都是一个三步骤
 *
 * @author Administrator
 * @date 2022/3/11 9:14
 */
public class HanNuoTa {
    public static void main(String[] args) {
        int n = 3;
        String a = "A柱", b = "B柱", c = "C柱";
        hannuota(a, b, c, n);
    }

    /**
     * 打印汉诺塔盘子移动轨迹方法
     * @param a 1号柱的名字
     * @param b 2号柱的名字
     * @param c 3号柱的名字
     * @param n 盘子的数量
     */
    public static void hannuota(String a, String b, String c, int n) {
        if (n == 1) {
            System.out.println("把第" + n + "个盘子从" + a + "移动到" + c);
        } else {
            //1.n-1的盘子看做一个整体,借助C从A移动到B
            hannuota(a, c, b, n - 1);
            //2.把第n个盘子,从A移动到C
            System.out.println("把第" + n + "个盘子从" + a + "移动到" + c);
            //3.再把n-1的盘子整体,借助A从B移动到C
            hannuota(b, a, c, n - 1);
        }
    }
}